package day;

/**
 * 639. 解码方法 II
 * 有问题
 */
public class P639 {
    final static int MOD = 100000007;

    public int numDecodings(String s) {
        int len = s.length();
        if (len < 1 || (len == 1 && s.charAt(0) == '0')) {
            return 0;
        }
        long[] dp = new long[len];
        if (s.charAt(0) == '0') {
            return 0;
        } else if (s.charAt(0) == '*') {
            dp[0] = 9;
        } else {
            dp[0] = 1;
        }

        for (int i = 1; i < len; i++) {
            long ppre = i - 2 >= 0 ? dp[i - 2] : 1;
            char pre = s.charAt(i - 1);
            char c = s.charAt(i);
            if (pre == '0' && c == '0') {
                return 0;
            }

            long sum = 0;
            if (pre == '*' && c == '*') {
                sum = (dp[i - 1] * 9 + ppre * 15) % MOD;
            } else if (pre == '*' && c != '*') {
                if (c == '0') {
                    sum = (ppre * 2) % MOD;
                } else {
                    sum = (dp[i - 1] + (c <= '6' ? 2 : 1) * ppre) % MOD;
                }
            } else if (pre != '*' && c == '*') {
                sum = (dp[i - 1] * 9 + (pre == '1' ? 9 : pre == '2' ? 6 : 0) * ppre) % MOD;
            } else {
                if (c == '0' && pre > '2') {
                    return 0;
                } else if (c == '0') {
                    sum = ppre;
                } else {
                    sum = dp[i - 1];
                    if (pre == '1' || (pre == '2' && c <= '6')) {
                        sum += ppre;
                    }
                    sum %= MOD;
                }
            }
            dp[i] = sum;
        }
        return (int) dp[len - 1];
    }

    public static void main(String[] args) {
        System.out.println(new P639().numDecodings("********"));
    }
}
